package de.jadehs.cosima.converters;

import java.text.CharacterIterator;
import java.text.StringCharacterIterator;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.UUID;

import org.eclipse.emf.ecore.util.EcoreUtil;
import org.jgrapht.DirectedGraph;

import de.jadehs.cosima.ANDExpression;
import de.jadehs.cosima.CosimaFactory;
import de.jadehs.cosima.CosimaUtil;
import de.jadehs.cosima.Expression;
import de.jadehs.cosima.IConverter;
import de.jadehs.cosima.KleeneExpression;
import de.jadehs.cosima.MultiState;
import de.jadehs.cosima.ORExpression;
import de.jadehs.cosima.ReadFromTape;
import de.jadehs.cosima.Regex;
import de.jadehs.cosima.State;
import de.jadehs.cosima.StateType;
import de.jadehs.cosima.StatesRegister;
import de.jadehs.cosima.StringExpression;
import de.jadehs.cosima.Transition;
import de.jadehs.cosima.TransitionsTable;

public class RegexToEpsNFAConverter implements
		IConverter<Regex, TransitionsTable> {

	public static final RegexToEpsNFAConverter INSTANCE = new RegexToEpsNFAConverter();
	private static final boolean OPTIMIZE = true;

	public TransitionsTable convert(Regex f) {
		TransitionsTable tt = CosimaFactory.eINSTANCE.createTransitionsTable();
		tt.setTape(EcoreUtil.copy(f.getTape()));
		tt.getTape().getAlphabet().add(CosimaUtil.EPSILON);
		StatesRegister reg = CosimaFactory.eINSTANCE.createStatesRegister();
		reg.setName("states" + System.currentTimeMillis());
		tt.setStates(reg);

		List<Transition> transitions = visit(f.getExpression());

		for (Transition t : transitions) {
			reg.getStates().add(t.getStart());
			reg.getStates().add(t.getEnd());
			tt.getTransitions().add(t);
		}

		long stateCount = 0;

		for (State s : reg.getStates()) {
			s.setName("q" + stateCount++);
		}

		if (!reg.getStates().isEmpty()) {
			reg.getStates().get(0).setStart(true);
			reg.getStates().get(reg.getStates().size() - 1)
					.setType(StateType.END);

			MultiState epsClosure = CosimaFactory.eINSTANCE.createMultiState();
			DirectedGraph<State, Transition> graph = TransitionsTableToDirectedGraphConverter.INSTANCE
					.convert(tt);

			for (State current : reg.getStates()) {
				epsClosure.getStates().clear();
				epsClosure.setType(StateType.NORMAL);
				EpsNFAToNFAConverter.createEpsilonClosure(graph, current,
						epsClosure);

				if (epsClosure.getType() == StateType.END) {
					current.setType(StateType.END);
				}
			}
		}

		return tt;
	}

	private List<Transition> visit(Expression expr) {
		if (expr instanceof StringExpression) {
			String input = ((StringExpression) expr).getInput();
			return createTransitions(input);
		} else if (expr instanceof ANDExpression) {
			ANDExpression aexpr = (ANDExpression) expr;
			return handleExpression(aexpr);
		} else if (expr instanceof KleeneExpression) {
			KleeneExpression kexpr = (KleeneExpression) expr;
			return handleExpression(kexpr);
		} else if (expr instanceof ORExpression) {
			ORExpression aexpr = (ORExpression) expr;
			return handleExpression(aexpr);
		}

		return Collections.emptyList();
	}

	private List<Transition> handleExpression(ORExpression aexpr) {
		List<Transition> left = visit(aexpr.getLeft());
		List<Transition> right = visit(aexpr.getRight());

		if (left.isEmpty() && right.isEmpty()) {
			return Collections.emptyList();
		}

		if (left.isEmpty()) {
			return right;
		}

		if (right.isEmpty()) {
			return left;
		}

		State glueFirst = createState();
		State glueLast = createState();
		State firstOfLeft = left.get(0).getStart();
		State lastOfLeft = left.get(left.size() - 1).getEnd();
		State firstOfRight = right.get(0).getStart();
		State lastOfRight = right.get(right.size() - 1).getEnd();

		List<Transition> merged = new ArrayList<Transition>();
		merged.add(createTransition(CosimaUtil.EPSILON, glueFirst, firstOfLeft));
		merged.add(createTransition(CosimaUtil.EPSILON, glueFirst, firstOfRight));
		merged.addAll(left);
		merged.addAll(right);
		merged.add(createTransition(CosimaUtil.EPSILON, lastOfLeft, glueLast));
		merged.add(createTransition(CosimaUtil.EPSILON, lastOfRight, glueLast));
		return merged;
	}

	private List<Transition> handleExpression(KleeneExpression kexpr) {
		List<Transition> list = visit(kexpr.getChildExpression());

		if (list.isEmpty()) {
			return Collections.emptyList();
		}

		List<Transition> merged = new ArrayList<Transition>();
		State first = list.get(0).getStart();
		State last = list.get(list.size() - 1).getEnd();

		if (OPTIMIZE) {
			merged.addAll(list);
			merged.add(createTransition(CosimaUtil.EPSILON, last, first));
		} else {
			State glueFirst = createState();
			State glueLast = createState();
			merged.add(createTransition(CosimaUtil.EPSILON, glueFirst, first));
			merged.addAll(list);
			merged.add(createTransition(CosimaUtil.EPSILON, last, glueLast));
			merged.add(createTransition(CosimaUtil.EPSILON, glueFirst, glueLast));
			merged.add(createTransition(CosimaUtil.EPSILON, glueLast, glueFirst));
		}

		merged.get(0).getStart().setType(StateType.END);
		merged.get(merged.size() - 1).getEnd().setType(StateType.END);

		return merged;
	}

	private List<Transition> handleExpression(ANDExpression aexpr) {
		List<Transition> left = visit(aexpr.getLeft());
		List<Transition> right = visit(aexpr.getRight());

		if (left.isEmpty() && right.isEmpty()) {
			return Collections.emptyList();
		}

		if (left.isEmpty()) {
			return right;
		}

		if (right.isEmpty()) {
			return left;
		}

		List<Transition> merged = new ArrayList<Transition>();
		merged.addAll(left);
		State lastOfLeft = left.get(left.size() - 1).getEnd();
		State firstOfRight = right.get(0).getStart();
		merged.add(createTransition(CosimaUtil.EPSILON, lastOfLeft,
				firstOfRight));
		merged.addAll(right);
		return merged;
	}

	private List<Transition> createTransitions(String input) {
		List<Transition> ret = new ArrayList<Transition>();

		if (input != null && input.length() > 0) {
			CharacterIterator iter = new StringCharacterIterator(input);
			char c = iter.first();
			State current = createState();

			do {
				State next = createState();
				ret.add(createTransition(c, current, next));
				current = next;
				c = iter.next();
			} while (c != CharacterIterator.DONE);
		}

		return ret;
	}

	private Transition createTransition(char c, State start, State end) {
		Transition t = CosimaFactory.eINSTANCE.createTransition();
		t.setStart(start);
		t.setEnd(end);
		ReadFromTape read = CosimaFactory.eINSTANCE.createReadFromTape();
		read.setSymbol(c);
		t.getStartInstructions().add(read);
		return t;
	}

	private State createState() {
		State ret = CosimaFactory.eINSTANCE.createState();
		ret.setName(UUID.randomUUID().toString());
		return ret;
	}
}
